from BinaryTree import Node as TreeNode
from BinaryTree import Tree
import collections


class Solution:
    def printTree(self, root: TreeNode):
        def get_depth(root):
            if not root:
                return 0
            return 1+ max(get_depth(root.left), get_depth(root.right))
        depth = get_depth(root)
        width = 2**depth-1
        res = [["" for _ in range(width)]for _ in range(depth)]

        def BFS(root, depth=None):
            if not root:
                return

            if depth is None:
                depth = get_depth(root)

            queue = collections.deque()
            queue.append(root)
            res = collections.deque()
            for _ in range(2**(depth)-1):
                node = queue.popleft()
                if node:
                    res.append(str(node.val))
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    res.append(None)
                    queue.append(node)
                    queue.append(node)
            return res

        tree = BFS(root)
        # tree = Solution._BFS(root)

        print('---', tree)
        for c in range(1, depth+1):
            n = 2**(c-1)  # 每层元素个数
            start = 2**(depth-c)-1  # 起始位置
            step = width - (2*start+1)
            if n != 1:
                step = step // (n-1)  # 间隔
            else:
                step = width
            for i in range(start, width, step):
                a = tree.popleft()
                if a:
                    res[c - 1][i] = a

                # if tree:
                #     a = tree.pop(0)
                #     if a:
                #         res[c-1][i] = a
                # else:
                #     res[c - 1][i] = None
        return res

    @staticmethod
    def _BFS(root, _n=False):
        """
        广度优先
        """
        if root is None:
            return

        # queue队列，保存节点
        queue = []
        # queue = collections.deque()
        # res = collections.deque()
        # vals，作为结果
        vals = []
        queue.append(root)

        while queue:
            # 拿出队首节点
            currentNode = queue.pop(0)

            vals.append(currentNode.val)
            print(currentNode.val, end=' ')
            if currentNode.left:
                queue.append(currentNode.left)
            if currentNode.right:
                queue.append(currentNode.right)
            else:
                # 每层最后一个时, 换行
                if _n:
                    print()
        return vals

    @staticmethod
    def show_tree_ls(tree_ls: list):
        for row in tree_ls:
            for data in row:
                if data == '':
                    print('_', end='')
                else:
                    print(data, end='')
            print()

    @staticmethod
    def show_ls(ls: list):
        for l in ls:
            print(l)

    @staticmethod
    def get_depth(root):
        if not root:
            return 0
        return 1 + max(Solution.get_depth(root.left), Solution.get_depth(root.right))

    @staticmethod
    def BFS(root, depth=None):
        if not root:
            return

        if depth is None:
            depth = Solution.get_depth(root)

        queue = collections.deque()
        queue.append(root)
        res = collections.deque()
        for _ in range(2 ** depth - 1):
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append(None)
                queue.append(node)
                queue.append(node)
        return res

if __name__ == '__main__':
    node = TreeNode(5)
    tree = Tree(node)

    for i in range(1, 10):
        # tree.insert(tree._root, i)
        tree.add(i)

    # tree.BFS(tree._root, True)

    sol = Solution()
    ret = sol.printTree(tree._root)

    # sol.BFS(tree._root)
    # sol.get_depth(tree._root)
    #
    # sol.show_ls(ret)
    sol.show_tree_ls(ret)

    # vals = sol.BFS(tree._root, True)
    # print(vals)



